using System.Linq;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0378. 有序矩阵中第K小的元素")]
    public class No0378_KthSmallest : AbsBaseTestItem
    {
        /*
        给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
        请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。
        */

        public override void OnTest()
        {
            int[][] matrix = null;
            int k = 0;

            matrix = new int[][] {
                new int[] { 01, 05, 09 },
                new int[] { 10, 11, 13 },
                new int[] { 12, 13, 15 },
            };
            k = 8;

            Assert.TestExe(KthSmallest, matrix, k, 13);
            Assert.TestExe(KthSmallest2, matrix, k, 13);
        }

        /// <summary>
        ///  方法一：直接排序
        /// 最直接的做法是将这个二维数组另存为为一维数组，并对该一维数组进行排序。
        /// 最后这个一维数组中的第 kkk 个数即为答案。
        /// </summary>
        public int KthSmallest(int[][] matrix, int k)
        {
            int rows = matrix.Length, columns = matrix[0].Length;
            int[] sorted = new int[rows * columns];
            int index = 0;
            foreach (int[] row in matrix)
            {
                foreach (int num in row)
                {
                    sorted[index++] = num;
                }
            }
            sorted = sorted.OrderBy(b => b).ToArray();
            return sorted[k - 1];
        }

        /// <summary>
        ///  方法三：二分查找
        /// </summary>
        public int KthSmallest2(int[][] matrix, int k)
        {
            int n = matrix.Length;
            int left = matrix[0][0];
            int right = matrix[n - 1][n - 1];

            bool check(int[][] matrix, int mid, int k, int n)
            {
                int i = n - 1;
                int j = 0;
                int num = 0;
                while (i >= 0 && j < n)
                {
                    if (matrix[i][j] <= mid)
                    {
                        num += i + 1;
                        j++;
                    }
                    else
                    {
                        i--;
                    }
                }
                return num >= k;
            };
            while (left < right)
            {
                int mid = left + ((right - left) >> 1);
                if (check(matrix, mid, k, n))
                {
                    right = mid;
                }
                else
                {
                    left = mid + 1;
                }
            }
            return left;
        }
    }
}
